package cn.corffen.test.algorithm.sort;

import com.corffen.libsource.StdRandom;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class SortDemo {

    public static final int TYPE_INSERT = 1;
    public static final int TYPE_SELECT = 2;
    public static final int TYPE_BUBBLE = 3;
    public static final int TYPE_SHELL = 4;
    public static final int TYPE_MERGE = 5;
    public static final int TYPE_MERGE_BU = 6;
    public static final int TYPE_QUICK = 7;
    public static final int TYPE_QUICK_LOOP = 8;
    public static final int TYPE_INSERTX = 9;
    public static final int TYPE_QUICK_3WAY = 10;

    public static List<Integer> types = new ArrayList<>();

    public static void main(String[] args) {

        types.add(TYPE_INSERT);
        types.add(TYPE_SELECT);
        types.add(TYPE_BUBBLE);
        types.add(TYPE_SHELL);
        types.add(TYPE_MERGE);
        types.add(TYPE_MERGE_BU);
        types.add(TYPE_QUICK);
        types.add(TYPE_QUICK_LOOP);
        types.add(TYPE_INSERTX);
        types.add(TYPE_QUICK_3WAY);

        Integer[] arr;
        for (Integer type : types) {
            arr = generateArr(100);
            System.out.println("排序前:" + printArr(arr));
            printSortArr(arr, type);
        }
    }

    private static String printArr(Integer[] arr) {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < arr.length; i++) {
            if (i % 20 == 0) {
                sb.append("\n");
            }
            sb.append(" " + arr[i] + " ");
        }
        sb.append(']');
        return sb.toString();
    }

    private static void printSortArr(Integer[] arr, int type) {
        long start = System.nanoTime();
        String sortName = "";
        switch (type) {
            case TYPE_INSERT:
                sortName = "插入";
                sortWithInsert(arr);
                break;
            case TYPE_INSERTX:
                sortName = "插入优化";
                sortWithInsertX(arr);
                break;
            case TYPE_SELECT:
                sortName = "选择";
                sortWithSelect(arr);
                break;
            case TYPE_BUBBLE:
                sortName = "冒泡";
                sortWithBubble(arr);
                break;
            case TYPE_SHELL:
                sortName = "希尔";
                sortWithShell(arr);
                break;
            case TYPE_MERGE:
                sortName = "归并";
                sortWithMerge(arr);
                break;
            case TYPE_MERGE_BU:
                sortName = "自底向上归并";
                sortWithMergeBu(arr);
                break;
            case TYPE_QUICK:
                sortName = "快速排序";
                sortWithQuick(arr);
                break;
            case TYPE_QUICK_LOOP:
                sortName = "非递归快速排序";
                sortWithQuickLoop(arr);
                break;
            case TYPE_QUICK_3WAY:
                sortName = "三向切分快速排序";
                quick3Way(arr);
                break;
            default:
                break;
        }
        System.out.println(sortName + "排序后:" + printArr(arr));
        long end = System.nanoTime();
        System.out.println(sortName + "用时:" + (end - start) + " 纳秒");
    }

    private static Integer[] generateArr(int n) {
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i;
        }
        StdRandom.shuffle(arr);
        return arr;
    }

    private static void swap(Object[] arr, int w, int v) {
        Object temp = arr[w];
        arr[w] = arr[v];
        arr[v] = temp;
    }

    private static <T> boolean less(Comparable<T> v, Comparable<T> w) {
        return v.compareTo((T) w) < 0;
    }

    /**
     * 遍历过程中,保证前面的元素都是有序的.
     * 从1开始.
     * 把1换成h,外面套一层while(h>=1)就是希尔排序
     *
     * @param a
     */
    private static void sortWithInsert(Comparable[] a) {
        int n = a.length;
        for (int i = 1; i < n; i++) {
            for (int j = i; j >= 1 && less(a[j], a[j - 1]); j--) {
                swap(a, j, j - 1);
            }
        }
    }

    private static void sortWithInsertX(Comparable[] a) {
        int exchanges = 0;
        int n = a.length;
        for (int i = n - 1; i > 0; i--) {
            if (less(a[i], a[i - 1])) {
                exchanges++;
                swap(a, i, i - 1);
            }
        }
        if (exchanges == 0) {
            return;
        }
        for (int i = 2; i < n; i++) {
            Comparable v = a[i];
            int j = i;
            while (less(v, a[j - 1])) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = v;
        }
    }

    /**
     * 每次选择一个最小的值,放入数组对应的角标中
     * 内层循环,起始位置是i+1,这样每次循环时,就会减少一个比较元素.
     * 时间复杂度为n方
     *
     * @param a
     */
    private static void sortWithSelect(Comparable[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int min = i;
            for (int j = i + 1; j < n; j++) {
                if (less(a[j], a[min])) {
                    min = j;
                }
            }
            swap(a, i, min);
        }
    }

    /**
     * 相邻元素进行比较,将较大值浮动到末端,然后每次内层循环的结束-i
     *
     * @param a
     */
    private static void sortWithBubble(Comparable[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            boolean isSorted = true;
            for (int j = 0; j < n - i - 1; j++) {
                if (less(a[j + 1], a[j])) {
                    isSorted = false;
                    swap(a, j + 1, j);
                }
            }
            if (isSorted) {
                break;
            }
        }
    }

    private static void sortWithShell(Comparable[] a) {
        int n = a.length;
        int h = 1;
        while (h < n / 3) {
            h = 3 * h + 1;
        }

        while (h >= 1) {
            for (int i = h; i < n; i++) {
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    swap(a, j, j - h);
                }
            }
            h /= 3;
        }
    }

    private static void sortWithMerge(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sortMerge(a, aux, 0, a.length - 1);
    }

    /**
     * 自底向上的归并排序
     * 1.外层len从1开始每次成倍的增长
     * 2.lo从0开始,小于n-len,每次lo+= 2*len
     * 3.计算mid和hi,注意hi不能越界,不能大于n-1
     * <p>
     * merger方法是合并两个有序的数组
     *
     * @param a
     */
    private static void sortWithMergeBu(Comparable[] a) {
        int n = a.length;
        Comparable[] aux = new Comparable[n];
        for (int len = 1; len < n; len *= 2) {
            for (int lo = 0; lo < n - len; lo += 2 * len) {
                int mid = lo + len - 1;
                int hi = Math.min(lo + len + len - 1, n - 1);
                merge(a, aux, lo, mid, hi);
            }
        }
    }

    /**
     * 求出mid值,然后递归调用merger方法,合并两个数组
     *
     * @param a
     * @param aux
     * @param lo
     * @param hi
     */
    private static void sortMerge(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sortMerge(a, aux, lo, mid);
        sortMerge(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    /**
     * 用i和j分别指向两个有序数组的开头
     * 然后移动i和j来比较元素的大小放进新的容器中.
     *
     * @param a
     * @param aux
     * @param lo
     * @param mid
     * @param hi
     */
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        for (int i = lo; i <= hi; i++) {
            aux[i] = a[i];
        }
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                a[k] = aux[j++];
            } else if (j > hi) {
                a[k] = aux[i++];
            } else if (less(aux[j], aux[i])) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }

    private static void sortWithQuick(Comparable[] a) {
        int n = a.length;
        sortQuick(a, 0, n - 1);
    }

    private static <T> void sortWithQuickLoop(Comparable<T>[] a) {
        sortWithQuickLoop(a, 0, a.length - 1);
    }

    /**
     * 用栈来存储lo和hi 每次求出切分值.
     *
     * @param a
     * @param lo
     * @param hi
     */
    private static void sortWithQuickLoop(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(lo);
        stack.push(hi);

        while (!stack.isEmpty()) {
            hi = stack.pop();
            lo = stack.pop();
            int partition = partition(a, lo, hi);
            if (partition - 1 > lo) {
                stack.push(lo);
                stack.push(partition - 1);
            }
            if (partition + 1 < hi) {
                stack.push(partition + 1);
                stack.push(hi);
            }
        }

    }

    private static void quick3Way(Comparable[] a) {
        sort3Way(a, 0, a.length - 1);
    }

    private static void sort3Way(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int lt = lo;
        int gt = hi;
        int i = lo + 1;
        Comparable v = a[lo];
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if (cmp < 0) {
                swap(a, lt++, i++);
            } else if (cmp > 0) {
                swap(a, i, gt--);
            } else {
                i++;
            }
        }
        sort3Way(a, lo, lt - 1);
        sort3Way(a, gt + 1, hi);
    }

    public void quickSortWith(int[] numbers) {
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(0);
        stack.push(numbers.length - 1);

        while (!stack.isEmpty()) {
            int hi = stack.pop();
            int lo = stack.pop();
            int partition = partition2(numbers, lo, hi);
            if (partition - 1 > lo) {
                stack.push(lo);
                stack.push(partition - 1);
            }
            if (partition + 1 < hi) {
                stack.push(partition + 1);
                stack.push(hi);
            }
        }
    }

    public int partition2(int[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        int v = a[lo];
        while (true) {
            while (a[++i] < v) {
                if (i == hi) {
                    break;
                }
            }
            while (v < a[--j]) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        int temp = a[lo];
        a[lo] = a[j];
        a[j] = temp;
        return j;
    }

    /**
     * 查找切分点并递归的调用快速排序
     *
     * @param a
     * @param lo
     * @param hi
     */
    private static void sortQuick(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int partition = partition(a, lo, hi);
        sortQuick(a, lo, partition - 1);
        sortQuick(a, partition + 1, hi);
    }

    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;

        Comparable v = a[lo];
        while (true) {
            while (less(a[++i], v)) {
                if (i == hi) break;
            }
            while (less(v, a[--j])) {
                if (j == lo) {
                    break;
                }
            }
            //如果左右指针有相遇,结束循环,并交换lo和j
            if (i >= j) {
                break;
            }
            //如果没有就交换i和j,继续下一次循环
            swap(a, i, j);
        }
        swap(a, lo, j);
        return j;
    }
}
